#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size(), INF = -0x3f3f3f3f, maxmoney = 0;
        vector<vector<int>> buy(n, vector<int>(k + 1, INF)), sell(n, vector<int>(k + 1, INF));
        buy[0][0] = -prices[0], sell[0][0] = 0;
        for (int i = 1; i < n; i++)
            for (int j = 0; j <= k; j++)
            {
                buy[i][j] = max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                sell[i][j] = sell[i - 1][j];
                if (j >= 1) sell[i][j] = max(sell[i][j], buy[i - 1][j - 1] + prices[i]);
            }

        for (int i = 0; i <= k; i++)
            maxmoney = max(maxmoney, sell[n - 1][i]);

        return maxmoney;
    }
};